package pers.qianyu.month_202012.date_20201220;

import org.junit.*;

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
 *
 * @author mizzle rain
 * @date 2020-12-20 17:19
 */
public class MissingNumber {
    // 异或法
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int res = len;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i] ^ i;
        }
        return res;
    }

    // 二分查找
    public int missingNumber2(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // 做差（一个一个加是为了防止溢出）
    public int missingNumber3(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res += i - nums[i];
        }
        return res;
    }

    @Test
    public void test1() {
        int result = new MissingNumber().missingNumber2(new int[]{0});
        System.out.println("result = " + result);
    }
}
